package mine.code.question.回溯;

import org.junit.Test;

import java.util.Arrays;

public class 解数独 {
    @Test
    public void run() {
        char[][] arr = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solveSudoku(arr);
        soutBoard(arr);
    }

    int[][][][] checkArr = new int[9][9][20][2];

    public void solveSudoku(char[][] board) {
        initCheckArr();
        putNum(board);
    }


    public boolean putNum(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (char k = '1'; k <= '9'; k++) {
                    if (valida(board, i, j, k)) {
                        board[i][j] = k;
                        if (putNum(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    /**
     * 初始化检验范围
     */
    private void initCheckArr() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int minX = i - i % 3;
                int minY = j - j % 3;
                int maxX = minX + 3;
                int maxY = minY + 3;
                int index = 0;
                for (int x = minX; x < maxX; x++) {
                    for (int y = minY; y < maxY; y++) {
                        if (x == i && y == j) {
                            continue;
                        }
                        checkArr[i][j][index][0] = x;
                        checkArr[i][j][index][1] = y;
                        index++;
                    }
                }
                for (int x = 0; x < 9; x++) {
                    if (x >= minX && x < maxX) {
                        continue;
                    }
                    checkArr[i][j][index][0] = x;
                    checkArr[i][j][index][1] = j;
                    index++;
                }
                for (int y = 0; y < 9; y++) {
                    if (y >= minY && y < maxY) {
                        continue;
                    }
                    checkArr[i][j][index][0] = i;
                    checkArr[i][j][index][1] = y;
                    index++;
                }
            }
        }
    }

    /**
     * 校验是否可以在(x,y)处放下 i
     *
     * @param board 数独
     * @param x     横坐标
     * @param y     纵坐标
     * @param i     放置数字
     * @return boolean
     */
    private boolean valida(char[][] board, int x, int y, char i) {
        int[][] xyCheckArr = checkArr[x][y];
        for (int[] arr : xyCheckArr) {
            int checkX = arr[0];
            int checkY = arr[1];
            if (board[checkX][checkY] == i) {
                return false;
            }
        }
        return true;
    }


    private void soutBoard(char[][] board) {
        System.out.println("-------");
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
        System.out.println("-------");
    }
}
